home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 February: Tool Chest / Dev.CD Feb 95 / Dev.CD Feb 95.toast / Tool Chest / Development Tools & Languages / Dylan Related / Mindy-1.1 (sources only) / mindy-1.1 / interp / sym.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-28  |  6.0 KB  |  276 lines  |  [TEXT/ttxt]
  1. /**********************************************************************\
  2. *
  3. *  Copyright (c) 1994  Carnegie Mellon University
  4. *  All rights reserved.
  5. *  
  6. *  Use and copying of this software and preparation of derivative
  7. *  works based on this software are permitted, including commercial
  8. *  use, provided that the following conditions are observed:
  9. *  
  10. *  1. This copyright notice must be retained in full on any copies
  11. *     and on appropriate parts of any derivative works.
  12. *  2. Documentation (paper or online) accompanying any system that
  13. *     incorporates this software, or any part of it, must acknowledge
  14. *     the contribution of the Gwydion Project at Carnegie Mellon
  15. *     University.
  16. *  
  17. *  This software is made available "as is".  Neither the authors nor
  18. *  Carnegie Mellon University make any warranty about the software,
  19. *  its performance, or its conformity to any specification.
  20. *  
  21. *  Bug reports, questions, comments, and suggestions should be sent by
  22. *  E-mail to the Internet address "gwydion-bugs@cs.cmu.edu".
  23. *
  24. ***********************************************************************
  25. *
  26. * $Header: sym.c,v 1.5 94/06/27 16:32:33 wlott Exp $
  27. *
  28. * This file implements symbols.
  29. *
  30. \**********************************************************************/
  31.  
  32. #include <stdio.h>
  33. #include <ctype.h>
  34.  
  35. #include "mindy.h"
  36. #include "gc.h"
  37. #include "bool.h"
  38. #include "class.h"
  39. #include "obj.h"
  40. #include "coll.h"
  41. #include "str.h"
  42. #include "def.h"
  43. #include "list.h"
  44. #include "type.h"
  45. #include "print.h"
  46. #include "sym.h"
  47.  
  48. obj_t obj_SymbolClass = NULL;
  49.  
  50. struct symbol {
  51.     obj_t class;
  52.     obj_t name;
  53.     obj_t next;
  54.     unsigned hash;
  55. };
  56.  
  57. static struct symtable {
  58.     obj_t class;
  59.     int entries;
  60.     int threshold;
  61.     int length;
  62.     obj_t *table;
  63. } Symbols;
  64.  
  65. static unsigned hash_name(char *name)
  66. {
  67.     unsigned char *ptr;
  68.     unsigned hash = 0;
  69.  
  70.     for (ptr = (unsigned char *)name; *ptr; ptr++)
  71.     hash = ((hash<<5)|(hash>>27)) ^ (*ptr & ~('a'^'A'));
  72.  
  73.     return hash;
  74. }
  75.  
  76. static boolean same_name(char *name1, char *name2)
  77. {
  78.     char c1, c2;
  79.  
  80.     while (1) {
  81.     c1 = *name1++;
  82.     c2 = *name2++;
  83.     
  84.     if (c1) {
  85.         if ((isupper(c1) ? tolower(c1) : c1)
  86.         != (isupper(c2) ? tolower(c2) : c2))
  87.         return FALSE;
  88.     }
  89.     else if (c2)
  90.         return FALSE;
  91.     else
  92.         return TRUE;
  93.     }
  94. }
  95.  
  96. static void rehash_table(struct symtable *table)
  97. {
  98.     int new_length;
  99.     obj_t *new_table;
  100.     obj_t *ptr;
  101.     int i;
  102.  
  103.     if (table->length < 1024)
  104.     new_length = table->length << 1;
  105.     else
  106.     new_length = table->length + 1024;
  107.  
  108.     new_table = (obj_t *)malloc(sizeof(obj_t)*new_length);
  109.  
  110.     ptr = new_table;
  111.     for (i = 0; i < new_length; i++)
  112.     *ptr++ = obj_False;
  113.  
  114.     ptr = table->table;
  115.     for (i = 0; i < table->length; i++) {
  116.     obj_t sym, next;
  117.     for (sym = *ptr++; sym != obj_False; sym = next) {
  118.         int index = obj_ptr(struct symbol *, sym)->hash % new_length;
  119.         next = obj_ptr(struct symbol *, sym)->next;
  120.         obj_ptr(struct symbol *, sym)->next = new_table[index];
  121.         new_table[index] = sym;
  122.     }
  123.     }
  124.  
  125.     free(table->table);
  126.     table->table = new_table;
  127.     table->length = new_length;
  128.     table->threshold = (new_length * 3) / 2;
  129. }
  130.  
  131. static obj_t intern(char *name, struct symtable *table)
  132. {
  133.     unsigned hash = hash_name(name);
  134.     int index = hash % table->length;
  135.     obj_t sym;
  136.  
  137.     for (sym = table->table[index];
  138.      sym != obj_False;
  139.      sym = obj_ptr(struct symbol *, sym)->next) {
  140.     if (obj_ptr(struct symbol *, sym)->hash == hash) {
  141.         obj_t sym_name = obj_ptr(struct symbol *, sym)->name;
  142.         if (same_name(name, obj_ptr(struct string *, sym_name)->chars))
  143.         return sym;
  144.     }
  145.     }
  146.  
  147.     sym = alloc(table->class, sizeof(struct symbol));
  148.     obj_ptr(struct symbol *, sym)->name = make_string(name);
  149.     obj_ptr(struct symbol *, sym)->next = table->table[index];
  150.     obj_ptr(struct symbol *, sym)->hash = hash;
  151.     table->table[index] = sym;
  152.     
  153.     table->entries++;
  154.     if (table->entries >= table->threshold)
  155.     rehash_table(table);
  156.  
  157.     return sym;
  158. }
  159.  
  160. obj_t symbol(char *name)
  161. {
  162.     return intern(name, &Symbols);
  163. }
  164.  
  165. char *sym_name(obj_t sym)
  166. {
  167.     obj_t string = obj_ptr(struct symbol *, sym)->name;
  168.  
  169.     return obj_ptr(struct string *, string)->chars;
  170. }
  171.  
  172. unsigned sym_hash(obj_t sym)
  173. {
  174.     return obj_ptr(struct symbol *, sym)->hash;
  175. }
  176.  
  177.  
  178.  
  179. /* Dylan functions. */
  180.  
  181. static obj_t string_as_symbol(obj_t class, obj_t string)
  182. {
  183.     return symbol(obj_ptr(struct string *, string)->chars);
  184. }
  185.  
  186. static obj_t symbol_as_string(obj_t class, obj_t symbol)
  187. {
  188.     return obj_ptr(struct symbol *, symbol)->name;
  189. }
  190.  
  191.  
  192. /* Printing. */
  193.  
  194. static void print_symbol(obj_t symbol)
  195. {
  196.     printf("%s", sym_name(symbol));
  197. }
  198.  
  199.  
  200. /* GC stuff. */
  201.  
  202. static int scav_sym(struct object *o)
  203. {
  204.     struct symbol *sym = (struct symbol *)o;
  205.  
  206.     scavenge(&sym->name);
  207.     scavenge(&sym->next);
  208.  
  209.     return sizeof(struct symbol);
  210. }
  211.  
  212. static obj_t trans_sym(obj_t sym)
  213. {
  214.     return transport(sym, sizeof(struct symbol));
  215. }
  216.  
  217. static void scav_table(struct symtable *table)
  218. {
  219.     int i;
  220.     obj_t *ptr;
  221.  
  222.     scavenge(&table->class);
  223.     ptr = table->table;
  224.     for (i = 0; i < table->length; i++)
  225.     scavenge(ptr++);
  226. }
  227.  
  228. void scavenge_symbol_roots(void)
  229. {
  230.     scavenge(&obj_SymbolClass);
  231.     scav_table(&Symbols);
  232. }
  233.  
  234.  
  235. /* Init stuff. */
  236.  
  237. void make_sym_classes(void)
  238. {
  239.     obj_SymbolClass = make_builtin_class(scav_sym, trans_sym);
  240. }
  241.  
  242. static void init_table(struct symtable *table, obj_t class)
  243. {
  244.     obj_t *ptr;
  245.     int i;
  246.  
  247.     table->class = class;
  248.     table->entries = 0;
  249.     table->threshold = 96;
  250.     table->length = 64;
  251.     table->table = (obj_t *)malloc(sizeof(obj_t)*64);
  252.     ptr = table->table;
  253.     for (i = 0; i < 64; i++)
  254.     *ptr++ = obj_False;
  255. }
  256.  
  257. void init_symbol_tables(void)
  258. {
  259.     init_table(&Symbols, obj_SymbolClass);
  260. }
  261.  
  262. void init_sym_classes(void)
  263. {
  264.     init_builtin_class(obj_SymbolClass, "<symbol>", obj_ObjectClass, NULL);
  265.     def_printer(obj_SymbolClass, print_symbol);
  266. }
  267.  
  268. void init_sym_functions(void)
  269. {
  270.     define_method("as", list2(singleton(obj_SymbolClass), obj_ByteStringClass),
  271.           FALSE, obj_False, FALSE, obj_SymbolClass, string_as_symbol);
  272.     define_method("as", list2(singleton(obj_StringClass), obj_SymbolClass),
  273.           FALSE, obj_False, FALSE, obj_ByteStringClass,
  274.           symbol_as_string);
  275. }
  276.